//---------------多源bfs最短路-----------------
//地图中的最高点
class Solution {
public:
    using PII = pair<int,int>;
    int dx[4] = {-1,1,0,0} , dy[4] = {0,0,-1,1};
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size() , n = isWater[0].size();
        vector<vector<int>> dis(m,vector<int>(n,-1));
        queue<PII> q;
        for(size_t i = 0 ; i < m ; ++i)
        {
            for(size_t j = 0 ; j < n ; ++j)
            {
                if(isWater[i][j] == 1) 
                {
                    q.push({i,j});
                    ++dis[i][j];
                }
            }
        }
        while(!q.empty())
        {
            auto [a,b] = q.front();
            q.pop();
            for(size_t i = 0 ; i < 4 ; ++i)
            {
                int y = a + dy[i] , x = b + dx[i];
                if(y >= 0 && x >= 0 && y < m && x < n && dis[y][x] == -1)
                {
                    dis[y][x] = dis[a][b] + 1;
                    q.push({y,x});
                }
            }
        }
        return dis;
    }
};

//地图分析
class Solution {
public:
    using PII = pair<int,int>;
    int dx[4] = {0,0,-1,1} , dy[4] = {-1,1,0,0};
    int maxDistance(vector<vector<int>>& grid) {
        //从陆地开始找
        int m = grid.size() , n = grid[0].size();
        queue<PII> q;
        vector<vector<int>> dis(m,vector<int>(n,-1));
        for(size_t i = 0 ; i < m ; ++i)
            for(size_t j = 0 ; j < n ; ++j)
                if(grid[i][j] == 1) q.push({i,j}),dis[i][j]++;
        int ret = -1;
        while(!q.empty())
        {
            auto [a,b] = q.front();
            q.pop();
            for(size_t i = 0 ; i < 4 ; ++i)
            {
                int y = a + dy[i] , x = b + dx[i];
                if(y >= 0 && x >= 0 && y < m && x < n && dis[y][x] == -1)
                {
                    q.push({y,x});
                    dis[y][x] = dis[a][b] + 1;
                    ret = max(ret , dis[y][x]);
                }
            }
        }
        return ret;
    }
};

//----------------拓扑排序----------
//课程表1
class Solution {
public:
    bool canFinish(int n, vector<vector<int>>& prerequisites) {
        //建表
        unordered_map<int,vector<int>> out;//出度表
        vector<int> in(n);//入度表
        for(auto e : prerequisites)
        {
            int a = e[0] , b = e[1];
            out[b].push_back(a);
            in[a]++;
        }
        //拓扑排序
        queue<int> q;
        //找出所有入度为0的点
        for(size_t i = 0 ; i < in.size() ; ++i)
        {
            if(in[i] == 0) q.push(i);
        }
        //开始排序
        while(!q.empty())
        {
            auto temp = q.front(); q.pop();
            for(auto e : out[temp])
            {
                in[e]--;
                if(in[e] == 0) q.push(e);
            }
        }
        for(size_t i = 0 ; i < in.size() ; ++i)
        {
            if(in[i] != 0) return false;
        }
        return true;
    }
};

//课程表Ⅱ
class Solution {
public:
    vector<int> findOrder(int n, vector<vector<int>>& prerequisites) {
        //建图

        unordered_map<int,vector<int>> out;//出度表
        vector<int> in(n);//入度表
        vector<int> ret;
        for(auto e : prerequisites)
        {
            int a = e[0] , b = e[1];//b->a
            out[b].push_back(a);
            in[a]++;
        }
        //拓扑排序
        queue<int> q;
        for(size_t i = 0 ; i < in.size() ; ++i)
        {
            if(in[i] == 0) q.push(i);
        }
        //开始排序
        while(!q.empty())
        {
            auto temp = q.front();
            q.pop();
            ret.push_back(temp);
            for(auto e : out[temp])
            {
                --in[e];
                if(in[e] == 0) q.push(e);
            }
        }
        if(ret.size() < n-1) return {};
        else return ret;
    }
};